///\todo upgrade

//////////////////////////////////////////////////////////////////////////////////
//                                                                              //
//  This file is part of the buola project (https://code.google.com/p/buola/).  //
//                                                                              //
//  Copyright(c) 2007-2011 Xavi Gratal                                          //
//  gratal AT gmail DOT com                                                     //
//                                                                              //
//  Buola is free software: you can redistribute it and/or modify               //
//  it under the terms of the GNU General Public License as published by        //
//  the Free Software Foundation, either version 3 of the License, or           //
//  (at your option) any later version.                                         //
//                                                                              //
//  Buola is distributed in the hope that it will be useful,                    //
//  but WITHOUT ANY WARRANTY; without even the implied warranty of              //
//  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the               //
//  GNU General Public License for more details.                                //
//                                                                              //
//  You should have received a copy of the GNU General Public License           //
//  along with buola.  If not, see <http://www.gnu.org/licenses/>.              //
//                                                                              //
//////////////////////////////////////////////////////////////////////////////////

#ifndef _BUOLA_CONTAINER_CTRIE_H_
#define _BUOLA_CONTAINER_CTRIE_H_

#include <buola/buola.h>
#include <buola/io.h>
#include <buola/iterator/range.h>
#include <buola/functors/actors/unary.h>

namespace buola {
    
///\addtogroup container
///@{

/////////////////////////////////////////////////////////////////////////////////////////////////

/// trie

/// A trie (http://en.wikipedia.org/wiki/Trie) is an associative container where keys are a
/// sequence of elements, usually strings of characters. The elements are stored in a tree
/// where at the root is the empty key, and each node points to nodes which contain a key with
/// one element added at the end.
///
/// \tparam tKey the elements that form the keys. The actual key will be a sequence of elements.
/// \tParam tValue the type of the value associated to each key.
///
/////////////////////////////////////////////////////////////////////////////////////////////////
    
template<typename tKey,typename tValue>
class CTrie
{
    /// a node in the trie
    struct SNode
    {
        /// default constructor
        SNode()
            :   mChild(nullptr)
            ,   mSibling(nullptr)
            ,   mHasValue(false)
        {}
        
        /// initializes a node with a key element
        SNode(tKey pKey,SNode *pChild=nullptr,SNode *pSibling=nullptr)
            :   mChild(pChild)
            ,   mSibling(pSibling)
            ,   mKey(pKey)
            ,   mHasValue(false)
        {}

        /// destructor
        
        /// Destroys all nodes below and after this node.
        ~SNode()
        {
            delete mChild;
            delete mSibling;
        }

        /// destroys the value in this node and all nodes below and after it
        void Clear()
        {
            delete mChild;
            delete mSibling;
            mHasValue=false;
        }

        /// get all the values below this node
        
        /// \param pV a vector of values.
        /// \param pSiblings if it is true, include elements in siblings (for internal use).
        template<typename tPValue>
        void GetAll(std::vector<tPValue> &pV,bool pSiblings=false) const
        {
            if(mHasValue)
                pV.push_back(mValue);
            if(mChild)
                mChild->GetAll(pV,true);
            if(mSibling&&pSiblings)
                mSibling->GetAll(pV,true);
        }

        /// get all the keys below this node

        /// \param pV a vector of keys.
        /// \param pKey the partial key, including this node.
        /// \param pSiblings if it is true, include elements in siblings (for internal use).
        template<typename tKeyCont>
        void GetAllKeys(std::vector<tKeyCont> &pV,const tKeyCont &pKey,bool pSiblings=false) const
        {
            if(mHasValue)
                pV.push_back(pKey);
            if(mChild)
                mChild->GetAllKeys(pV,pKey+mChild->mKey,true);
            if(mSibling&&pSiblings)
                mSibling->GetAllKeys(pV,pKey+mSibling->mKey,true);
        }

        /// get all the values below this node for which the predicate holds on the value
        
        /// \param pV a vector of values.
        /// \param pFunc a unary function which takes a \a tValue as a parameter
        /// \param pSiblings if it is true, include elements in siblings (for internal use).
        template<typename tFunc,typename tPValue>
        void GetAllIf(std::vector<tPValue> &pV,const tFunc &pFunc,bool pSiblings=false) const
        {
            if(mHasValue&&pFunc(mValue))
                pV.push_back(mValue);
            if(mChild)
                mChild->GetAllIf(pV,pFunc,true);
            if(mSibling&&pSiblings)
                mSibling->GetAllIf(pV,pFunc,true);
        }

        /// get all the keys below this node for which the predicate holds on the value
        
        /// \param pV a vector of keys.
        /// \param pKey the partial key, including this node.
        /// \param pFunc a unary function which takes a \a tValue as a parameter
        /// \param pSiblings if it is true, include elements in siblings (for internal use).
        template<typename tKeyCont,typename tFunc>
        void GetAllKeysIf(std::vector<tKeyCont> &pV,const tKeyCont &pKey,const tFunc &pFunc,bool pSiblings=false) const
        {
            if(mHasValue&&pFunc(mValue))
                pV.push_back(pKey);
            if(mChild)
                mChild->GetAllKeysIf(pV,pKey+mChild->mKey,pFunc,true);
            if(mSibling&&pSiblings)
                mSibling->GetAllKeysIf(pV,pKey+mSibling->mKey,pFunc,true);
        }

        SNode *mChild;      ///< the child node
        SNode *mSibling;    ///< the next sibling
        tKey mKey;          ///< the key element stored in this node
        bool mHasValue;     ///< true if the element has a value
        tValue mValue;      ///< the value stored in the node
    };

public:
    /// default constructor
    CTrie()
    {}
    
    /// destructor
    ~CTrie()
    {}
    
private:
    /// traverses the nodes matching the elements in the iterator range, calling \p pFunc for each node
    
    /// upon return, pS points to the first character not matched
    template<typename tIt,typename tFunc>
    void Traverse(tIt &pS,const tIt &pE,tFunc pFunc) const
    {
        SNode *lNode=mRoot.mChild;
        pFunc(const_cast<SNode*>(&mRoot));
        
        if(pS==pE) return;
        
        while(lNode)
        {
            if(*pS==lNode->mKey)
            {
                pFunc(lNode);
                
                if(++pS==pE)
                    return;
                lNode=lNode->mChild;
            }
            else
                lNode=lNode->mSibling;
        }
    }
    
    /// finds as many characters from the iterator range as it can, returning a pointer to the longest match
    
    /// upon return, pS points to the first character not matched
    template<typename tIt>
    SNode *FindNode(tIt &pS,const tIt &pE)
    {
        SNode *lReturn=nullptr;
        Traverse(pS,pE,fn::assign_to(lReturn));
        return lReturn;
    }

    /// finds as many characters from the iterator range as it can, returning a pointer to the longest match
    
    /// upon return, pS points to the first character not matched (const version)
    template<typename tIt>
    const SNode *FindNode(tIt &pS,const tIt &pE) const
    {
        const SNode *lReturn=nullptr;
        Traverse(pS,pE,fn::assign_to(lReturn));
        return lReturn;
    }

    /// finds as many characters from the iterator range as it can, returning the whole path
    
    /// upon return, pS points to the first character not matched
    template<typename tIt>
    std::vector<SNode*> FindPath(tIt &pS,const tIt &pE)
    {
        std::vector<SNode*> lReturn;
        Traverse(pS,pE,fn::push_back_into(lReturn));
        return lReturn;
    }

    /// finds as many characters from the iterator range as it can, returning a pointer to the longest match with a key
    
    /// upon return, pS points to the first character not matched
    template<typename tIt>
    const SNode *FindValueNode(tIt &pS,const tIt &pE) const
    {
        const SNode *lNode=mRoot.mChild;
        const SNode *lReturn=mRoot.mHasValue?&mRoot:nullptr;

        if(pS==pE) return lReturn;

        tIt lI=pS;
        
        while(lNode)
        {
            if(*lI==lNode->mKey)
            {
                ++lI;

                if(lNode->mHasValue)
                {
                    pS=lI;
                    lReturn=lNode;
                }
                
                if(lI==pE)
                    break;
                lNode=lNode->mChild;
            }
            else
                lNode=lNode->mSibling;
        }
        return lReturn;
    }

public:
    /// deletes the root node, emptying the trie

    /// \post Empty()==true
    void clear()
    {
        mRoot.Clear();
    }
    
    /// returns true if the trie is empty, false otherwise
    bool empty() const
    {
        return !(mRoot.mChild||mRoot.mHasValue);
    }
    
    /// adds a value to the trie
    template<typename tIt,typename tPValue>
    void Add(tIt pS,tIt pE,tPValue &&pValue)
    {
        SNode *lNode=FindNode(pS,pE);
        
        while(pS!=pE) //the exact node was not found... create it
        {
            lNode->mChild=new SNode(*pS,nullptr,lNode->mChild);
            lNode=lNode->mChild;
            ++pS;
        }

        lNode->mHasValue=true;
        lNode->mValue=std::forward<tPValue>(pValue);
    }

    /// adds a value to the trie (range version)
    template<typename tRange,typename tPValue>
    void Add(const tRange &pRange,tPValue &&pValue)
    {
        Add(range_begin(pRange),range_end(pRange),std::forward<tPValue>(pValue));
    }

    /// removes a value from the trie
    template<typename tIt>
    void Remove(tIt pS,tIt pE)
    {
        std::vector<SNode*> lPath=FindPath(pS,pE);
                
        if(pS!=pE) return; //it wasn't there, do nothing

        lPath.back()->mHasValue=false;

        for(auto i=lPath.rbegin();i!=lPath.rend()-1;++i)
        {
            SNode *lNode=*i;
            if(lNode->mHasValue) break;
            if(lNode->mChild) break;
            
            //remove it from parent
            SNode *lParent=*(i+1);
            if(lParent->mChild==lNode)
            {
                lParent->mChild=lNode->mSibling;
            }
            else
            {
                SNode *lSibling=lParent->mChild;
                while(lSibling->mSibling!=lNode)
                    lSibling=lSibling->mSibling;
                lSibling->mSibling=lNode->mSibling;
            }
            delete lNode;
        }
    }

    /// removes a value from the trie (range version)
    template<typename tRange>
    void Remove(const tRange &pRange)
    {
        Remove(range_begin(pRange),range_end(pRange));
    }

    /// gets a value from the trie
    
    /// This is the simplest interface to the trie, and it works in an all or nothing fashion.
    /// In case of a succesful match, pS points to the end of the string.
    ///
    /// For example, if the trie contains the entries to and tonto:
    ///  - searching for ton yields nothing, pS is unchanged
    ///  - searching for tonto yields the value of tonto, pS points to the end of the input
    ///  - searching for tock yields nothing, pS is unchanged
    template<typename tIt>
    const tValue *Get(tIt &pS,const tIt &pE) const
    {
        tIt lI=pS;
        const SNode *lNode=FindNode(lI,pE);
        
        if(!lNode->mHasValue||lI!=pE)
            return nullptr;
        pS=pE;
        return &lNode->mValue;
    }

    /// gets a value from the trie (const iterator version)
    template<typename tIt>
    const tValue *Get(const tIt &pS,const tIt &pE) const
    {
        tIt lI=pS;
        return Get(lI,pE);
    }

    /// gets a value from the trie (range version)
    template<typename tRange>
    const tValue *Get(const tRange &pRange) const
    {
        return Get(range_begin(pRange),range_end(pRange));
    }
    
    /// gets the longest complete match from the input
    
    /// This is similar to Get, except that not all the input must be matched. It returns the longest key found
    /// at the beginning of the input. Upon a succesful match, pS points to the first item not matched. If there
    /// is no match, pS is unchanged
    ///
    /// For example, if the trie contains the entries to and tonto:
    ///  - searching for ton yields the value of to, pS points to the 'n'
    ///  - searching for tonto yields the value of tonto, pS points to the end of the input
    ///  - searching for tock yields the value of to, pS points to the 'c'
    template<typename tIt>
    const tValue *GetLongest(tIt &pS,const tIt &pE) const
    {
        tIt lI=pS;
        const SNode *lNode=FindValueNode(lI,pE);
        
        if(!lNode)
            return nullptr;
        pS=lI;
        return &lNode->mValue;
    }

    /// gets the longest complete match from the input (const iterator version)
    template<typename tIt>
    const tValue *GetLongest(const tIt &pS,const tIt &pE) const
    {
        tIt lI=pS;
        return GetLongest(lI,pE);
    }

    /// gets the longest complete match from the input (range version)
    template<typename tRange>
    const tValue *GetLongest(const tRange &pRange) const
    {
        return GetLongest(range_begin(pRange),range_end(pRange));
    }
    
    /// finds a value in the trie

    /// This is the most flexible interface. It tries to match as many characters as possible, and it allows searching
    /// for prefixes. Upon return, pS points to the first item not matched in the input string.
    /// If the longest prefix matched contains a value, it is returned.
    ///
    /// For example, if the trie contains the entries to and tonto:
    ///  - searching for ton yields nothing, pS points to the end of the input.
    ///  - searching for tonto yields the value of tonto, pS points to the end of the input.
    ///  - searching for tock yields the value of to, pS points to the 'c' in the input
    template<typename tIt>
    const tValue *Find(tIt &pS,const tIt &pE) const
    {
        const SNode *lNode=FindNode(pS,pE);
        if(lNode->mHasValue)
            return &lNode->mValue;
        return nullptr;
    }

    /// finds all values starting with a certain prefix
    
    /// Doesn't modify \p pS
    template<typename tIt,typename tPValue>
    void FindAll(const tIt &pS,const tIt &pE,std::vector<tPValue> &pValue) const
    {
        tIt lI=pS;
        const SNode *lNode=FindNode(lI,pE);
        
        if(lI!=pE) return;
        
        lNode->GetAll(pValue);
    }

    /// finds all values starting with a certain prefix (range version)
    template<typename tRange,typename tPValue>
    void FindAll(const tRange &pRange,std::vector<tPValue> &pValue) const
    {
        FindAll(range_begin(pRange),range_end(pRange),pValue);
    }

    /// finds all keys starting with a certain prefix
    
    /// Doesn't modify \p pS
    template<typename tIt,typename tKeyCont>
    void FindAllKeys(const tIt &pS,const tIt &pE,std::vector<tKeyCont> &pValue) const
    {
        tIt lI=pS;
        const SNode *lNode=FindNode(lI,pE);
        
        if(lI!=pE) return;
        
        tKeyCont lKey(pS,pE);
        
        lNode->GetAllKeys(pValue,lKey);
    }

    /// finds all keys starting with a certain prefix (range version)
    template<typename tRange,typename tKeyCont>
    void FindAllKeys(const tRange &pRange,std::vector<tKeyCont> &pValue) const
    {
        FindAllKeys(range_begin(pRange),range_end(pRange),pValue);
    }

    /// finds all values starting with a certain prefix for which \p pPred returns \c true
    
    /// Doesn't modify \p pS
    template<typename tIt,typename tFunc,typename tPValue>
    void FindAllIf(const tIt &pS,const tIt &pE,std::vector<tPValue> &pValue,const tFunc &pPred) const
    {
        tIt lI=pS;
        const SNode *lNode=FindNode(lI,pE);
        
        if(lI!=pE) return;
        
        lNode->GetAllIf(pValue,pPred);
    }

    /// finds all values starting with a certain prefix (range version)
    template<typename tRange,typename tFunc,typename tPValue>
    void FindAllIf(const tRange &pRange,std::vector<tPValue> &pValue,const tFunc &pPred) const
    {
        FindAllIf(range_begin(pRange),range_end(pRange),pValue,pPred);
    }

    /// finds all keys starting with a certain prefix for which \p pPred returns \c true
    
    /// Doesn't modify \p pS.
    ///
    /// Even though keys are returned, the predicate is still evaluated on the values.
    template<typename tIt,typename tKeyCont,typename tFunc>
    void FindAllKeysIf(const tIt &pS,const tIt &pE,std::vector<tKeyCont> &pValue,const tFunc &pPred) const
    {
        tIt lI=pS;
        const SNode *lNode=FindNode(lI,pE);
        
        if(lI!=pE) return;
        
        tKeyCont lKey(pS,pE);
        
        lNode->GetAllKeysIf(pValue,lKey,pPred);
    }

    /// finds all keys starting with a certain prefix (range version)
    template<typename tRange,typename tKeyCont,typename tFunc>
    void FindAllKeysIf(const tRange &pRange,std::vector<tKeyCont> &pValue,const tFunc &pPred) const
    {
        FindAllKeysIf(range_begin(pRange),range_end(pRange),pValue,pPred);
    }

    /// gets a value from the trie
    
    /// \throws XNotFound if the key is not found
    template<typename tRange>
    const tValue &operator[](const tRange &pRange) const
    {
        const tValue *lValue=Get(pRange);
        if(!lValue)
            throw XNotFound("key not found in trie");
        return *lValue;
    }

    /// outputs the content of the trie (useful for debugging)
    void Dump(SNode *pNode=nullptr,int pDepth=0)
    {
        if(!pNode)
        {
            if(!mRoot.mChild) return;
            pNode=mRoot.mChild;
        }
        
        for(int i=0;i<pDepth;i++)
            msg_info() << "   ";
        
        msg_info() << (char)pNode->mKey << ' ' << pNode->mHasValue << ' ' << pNode->mValue << "\n";
        
        if(pNode->mChild)
            Dump(pNode->mChild,pDepth+1);
        if(pNode->mSibling)
            Dump(pNode->mSibling,pDepth);            
    }

private:
    /// represents the empty string. It can have children and a value, but it cannot have siblings.
    SNode mRoot;
};

///@}

/*namespace buola*/ }

#endif
